The FEC (forward error correction) method is known as a method for compensating for bit errors and losses in digital data. By the FEC method, the transmitting side encodes data according to an error correction code and the receiving side detects and corrects for errors or losses. Various codes such as the BCH code, Reed-Solomon code, and convolutional code have been proposed as error correction codes (refer to Non-patent document 1, for example).
An error correction code includes a bit string of (N+n) bits in which an n-bit error correction code is added to N-bit data which is called “codeword.” With occurrence of bit errors in a codeword, the receiving side can detect error positions and hence can correct the errors completely as long as the number of errors is within the error correction capability. The error correction capability depends on the error correction code. For example, a (15, 10) Hamming code, that is, a Hamming code in which 15-bit codeword is formed by adding a 5-bit error correction code to 10-bit data, can correct a burst error of up to 2 bits. Although error detection codes as typified by the parity code and the CRC code add an error detection code to data like error correction codes do, they merely detect errors in codewords and cannot correct errors.
To cope with errors such as burst errors that are difficult to correct by an error correction code alone, various FEC methods have been proposed and used in which plural kinds of error correction codes are combined or an error correction code and an error detection code are combined.
The conventional FEC methods are generally classified into three. The first method is an FEC method which is used in a stream-type transmission system. The second method is an FEC method for compensating for packet losses in a packet-type transmission system. The third method is an FEC method for correcting for packet losses and bit errors in a packet in a packet-type transmission system. Conventional FEC methods will be described below with reference to FIGS. 6-9.
FIG. 6 is charts illustrating an FEC method which is used in a stream-type transmission system. FIG. 6(a) shows a system using one kind of error correction code, and FIG. 6(b) shows a system using two kinds of error correction codes.
In the system of FIG. 6(a) which uses one kind of error correction code, in the transmitting side, transmission data are divided in units of a predetermined number of bits and codewords are generated by calculating an error correction code for each piece of divided data. In the receiving side, errors are corrected by using the error correction codes.
FIG. 6(b) shows a system using a code called “product code” which is a combination of two kinds of error correction codes. As shown in FIG. 6(b), data having a certain length are arranged in a matrix format. For example, first, error correction codes are calculated in the vertical direction (column direction) and an outer code which is an error correction code is added at the end of each column. The term “outer code” means a code, calculated first, of the two kinds of codes used.
Then, error correction codes are calculated in the horizontal direction (row direction) and an inner code which is an error correction code is added at the end of each row. The term “inner code” means a code, calculated later, of the two kinds of codes used.
In product codes, even when, for example, errors occur in one row due to a burst error in such a number as to exceed the error correction ability of the inner code, no burst error exists in the column direction and hence all the errors can be corrected by the outer codes. The error correction ability is thus increased. For example, in Japan, the ground-wave digital broadcast employs an FEC method using a product code in which the inner code and the outer code are a punctured convolutional code and a (204, 188) shortened Reed-Solomon code, respectively (refer to Non-patent documents 2 and 3, for example).
FIG. 7 is a chart illustrating an FEC method for compensating for a packet loss in a packet-type transmission system, which is described in Patent document 1. According to Patent document 1, as shown in FIG. 7, a parity cell having parity bits in a payload portion is transmitted following ATM cells having data A-D in payload portions. A parity bit for the kth bits of the data A-D is put in the kth bit of the payload portion of the parity cell. The ATM cells are assigned consecutive cell numbers in transmission order.
For example, when the ATM cell having the data B was lost, the receiving side can recognize the cell loss from the cell numbers and restore the data B using the parity cell. Although capable of compensating for a packet loss with a simple scheme, this system cannot correct bit errors. That is, when an error has occurred at the first bit of the data B, the parity cell can only judge that an error or errors have occurred in one or plural ones of the first bits of the data A-D.
FIGS. 8 and 9 are charts illustrating an FEC method for correcting for packet losses and errors in a packet in a packet-type transmission system, which is described in Non-patent document 4 and Patent documents 2 and 3, for example.
In this method, as shown in FIG. 8(a), a data sequence is divided into data A-D having a predetermined length, which are then arranged in a matrix format. Outer codes A-D are calculated in the row direction and assigned to the data A-D, respectively. Then, inner codes are calculated in the column direction for the data and the outer codes, and an inner code Z is assigned to them. A product code is thus calculated.
Then, the data of each row is divided into data having an ATM cell size, which are transmitted in order from the first row of the matrix as ATM cells which are assigned respective cell numbers indicating the cell transmission order. In FIG. 8(b), each piece of data is divided into two pieces of data.
In the receiving side, as shown in FIG. 9, the data are arranged in the same matrix format as in the transmitting side on the basis of the cell numbers. In doing so, dummy data is inserted for a lost cell (its disappearance can be detected according to the cell numbers). In FIG. 9, since the ATM cell of the data B-1 has disappeared, dummy data is inserted at the position of the data B-1. Data with errors cannot be detected at this stage, and hence data, if any, still having errors is included in the matrix. In FIG. 9, errors have occurred in the data D-2.
Subsequently, the data which are arranged in a matrix form are subjected to error correction processing using the inner codes and the outer codes, whereby the dummy data and the error are corrected. Unlike the scheme of Patent document 1 which has been described above with reference to FIG. 7, this method can also compensate for bit errors. However, this method has drawbacks of low transmission efficiency, a long delay, and a complexity of the circuit.
The low transmission efficiency is due to the presence of dedicated cells which contain outer codes. For example, Non-patent document 4 describes that a (442, 424) BCH code provides transmission efficiency of 21/22 and a (460, 424) BCH code provides transmission efficiency of 10/11.
A long delay occurs at the time of error correction in the receiving side, and depends on the time taken to receive all codewords, that is, data, inner codes, and outer codes. For example, Non-patent document 4 describes a method in which a (460, 424) BCH code is used as the outer code and a (15, 14) parity code is used as the inner code, the codeword length in the horizontal direction (data plus an outer code) is 11 cells, the codeword length in the vertical direction (data plus an inner code) is 15 cells, and the codeword length of the entire product code is 11×15=165 cells. That is, the time taken to receive 165 cells determines the delay time.
Furthermore, where an error correction code is used for each of the inner code and the outer code, a complex circuit configuration is necessary. Incidentally, an error correction encoder which performs error correction encoding, an error corrector which performs error correction according to an error correction code, an error detection encoder which performs error detection encoding, and an error detector which performs error detection according to an error detection code are described in Non-patent document 5, for example.
A method for performing two-dimensional encoding according to the turbo product code like a method using a product code has been proposed. However, the turbo product code requires a large amount of calculation. In particular, in decoding, repetitive operations are necessary and the processing becomes complex. A method using the turbo product code is described in Patent document 4, for example.
Patent document 1: Japanese Patent No. 2,762,815
Patent document 2: JP-A-03-254240
Patent document 3: JP-A-04-207734
Patent document 4: US 2004-0260996A1
Non-patent document 1: “Electronics Essentials No. 20, Essential Points of Error Correction Codes,” supervised by Hideki Imai, Japan Industry Center.
Non-patent document 2: “Digital Broadcasting Systems Handbook,” supervised by Osamu Yamada, edited by the Institute of Image Information and Television Engineers, Ohmsha Ltd., pp. 18-19.
Non-patent document 3: ITU-R Recommendation BT. 1306-1
Non-patent document 4: Ryoichi Iwase and Hitoshi Obara, “A Bit Error and Cell Loss Compensation Method for ATM Transport Systems,” Japanese-language Transactions of the Institute of Electronics, Information and Communication Engineers, J75-B1, No. 1, pp. 1-11, January 1992.
Non-patent document 5: “Application Examples of Error Correction Encoding Techniques <Digital Recording Edition>,” supervised by Hiroshi Harashima, published by Triceps Co., Ltd., pp. 43-44 and pp. 67-68